/*
 * exame_2009_10_junho_btreeAPI.c
 *
 *  Created on: Jun 19, 2012
 *      Author: ubuntu
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "exame_2009_10_junho_types.h"

// Remove elemento valor da Arvore a
// retorna (n de elementos q removeu)
// Nodo Root da arvore binária
int remover(ArvBin a, int valor) {

	// tratar o caso de estarmnos a remover o elemento root
	ArvBin root = a;

	// encontrar o nodo e manter o registo do destino
	if (a == NULL) {
		return NULL;
	}
	ArvBin nodoAux = a;
	ArvBin * destino = NULL;

	while (nodoAux != NULL && valor != nodoAux->valor) {

		if (valor < nodoAux->valor) {
			destino = &(nodoAux->esq);
			nodoAux = nodoAux->esq;
		} else {
			destino = &(nodoAux->dir);
			nodoAux = nodoAux->dir;
		}
	}
	// guardar a ref do esq e guardar a ref do direito

	ArvBin dir = NULL;
	ArvBin esq = NULL;

	if (nodoAux == NULL) {
		// Nodo a remover, não existe
		return root;
	} else {
		esq = nodoAux->esq;
		dir = nodoAux->dir;
	}

	// Tratar do ramo direito
	if (destino != NULL) {
		*destino = dir;
	}

	// Tratar do ramo esquerdo
	if (esq != NULL) {
		ArvBin * destino2 = NULL;
		ArvBin puta = dir;
		while (puta != NULL) {
			if (esq->valor puta->valor) {
			}

		}
	}

// Adicina, em modo ordenado, valor na Arvore a
// retorna
// retorna apontador para novo nodo se adicinou
// NULL se n adicionou
	ArvBin adicionar(ArvBin a, int valor) {

		if (a == NULL) {
			return NULL;
		}

// Encontrar poiso
		ArvBin nodo = a;
		ArvBin * destino = NULL;
		while (nodo != NULL) {
			if (valor < nodo->valor) {
				destino = &(nodo->esq);
				nodo = nodo->esq;
			} else {
				destino = &(nodo->dir);
				nodo = nodo->dir;
			}
		}

// Criar casulo
		ArvBin novoNodo = (ArvBin) malloc(sizeof(NodoArvBin));

		novoNodo->valor = valor;
		novoNodo->esq = NULL;
		novoNodo->dir = NULL;

//deixar casulo no poiso
		*destino = novoNodo;

		return novoNodo;

	}

	int contaNodos(ArvBin a) {

//condição de paragem
		if (a == NULL) {
			return 0;
		}

		return 1 + contaNodos(a->esq) + contaNodos(a->dir);
	}

// Verificaa existencia do valor na arvore a
// Retorna
// 1 se existe
// 0 se nao existe
	int existe(ArvBin a, int valor) {

		int boolean = 0;

		ArvBin nodo = a;

		while (nodo != NULL) {

			if (nodo->valor == valor) {
				boolean = 1;
				break;
			}

			if (valor < nodo->valor) {
				nodo = nodo->esq;
			} else {
				nodo = nodo->dir;
			}
		}

		return boolean;
	}
